package algorithms.a03sortadvance;

import algorithms.utis.AlgorithmsUtis;
import algorithms.utis.SortTestHelper;
import org.apache.commons.lang3.RandomUtils;

import java.util.ArrayList;

/**
 * 用快速排序计算数组中第M大的元素
 *
 * @author 王昊然
 * @create 2018-02-06 11:39
 **/
public class QuickSortCalNumberM {

    /**
     * 自顶向下的归并排序
     *
     * @param arr
     * @date: 2018/2/6 16:10
     * @author: 王昊然
     */
    public static void sort(Comparable[] arr, int M) {
        int n = arr.length;
        System.out.println("求第" + M + "大元素的值");
        int station = partition3Way(arr, 0, n - 1, M);
        System.out.println("下标"+station+ ",值" + arr[station]);
    }

    /**
     * 三路partition
     * 更适用于重复性很强的数组
     *
     * @param arr
     * @param v   起始下标
     * @param r   最大下标
     * @param M   求第M大的元素
     * @return 第M大元素对应的下标
     * @date: 2018-02-06 下午 11:32
     * @author: 王昊然
     */
    private static int partition3Way(Comparable[] arr, int v, int r, int M) {

        if (v >= r) return 0;

        //如果是近乎有序的数组，每次取第一个作为v不平衡性大，效率低，取随机位置进行优化
        int random = RandomUtils.nextInt(v, r);
        AlgorithmsUtis.swap(arr, v, random);

        int lt = v;
        int gt = r + 1;
        int i = v + 1;
        while (i < gt) {
            if (arr[i].compareTo(arr[v]) == 0) {
                i++;
            } else if (arr[i].compareTo(arr[v]) < 0) {
                AlgorithmsUtis.swap(arr, i, lt + 1);
                lt++;
                i++;
            } else if (arr[i].compareTo(arr[v]) > 0) {
                AlgorithmsUtis.swap(arr, i, gt - 1);
                gt--;
            }
        }

        AlgorithmsUtis.swap(arr, v, lt);

        if (arr.length - gt >= M)
            return partition3Way(arr, gt, r, M);

        else if (arr.length - lt >= M)
            return gt - 1;//此时M位于lt--gt之间，都是相等的值，返回区间任一位置都可以

        else
            return partition3Way(arr, v, lt - 1, M - arr.length + lt);
    }


    public static void main(String[] args) {
        int N = 20;
        //Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 20); //1排序数组数值范围小，插入排序优势明显
//        Integer[] arr = SortTestHelper.generateNearlyOrderedArray(N, 100);
        Integer[] arr = new Integer[]{5,16,13,7, 18, 16, 15, 9, 18, 6, 9, 1, 14, 3, 17, 4, 17, 8, 6, 13};
        System.out.println(SortTestHelper.printArray(arr));

        new ArrayList<>();

       sort(arr, 3);
    }

}
